Interprocedural Analysis

今日推荐歌曲：R&B歌曲 别问很可怕-J.Sheon

可惜一溪风月,莫教踏碎琼瑶

Motivation

过程内的分析未考虑函数调用，导致分析不精确，例如存在如下程序（常量传播，Constant Propagation）

Inraprocedural analysis为了safe-approximation会采用最保守的假设，也就是假设方法调用可以做任何事情，基于这种过于保守的假设，在Inraprocedural analysis下，会认为：

n = NAC x = NAC, y = NAC

所以需要使用过程间分析：Inter-procedural Analysis，考虑函数调用，又称为全程序分析（Whole Program Analysis），需要构建调用图，加入 Call edges 和 Return edges

Call Graph Construction

本质是调用边的集合，从调用点（call-sites）到目标函数（target methods / callees）的边

Call Graph Construction

越往上，速度越快，但是精度越低，越往下速度越慢，但是精度越高。主要学习的就是CHA和k-CFA算法

Method Calls(Invocations) in Java

在java中的调用类型为三类 其中Virtual Call主要应用于多态，因为多态，其目标方法只能在运行时确定；在Java中，认为除了静态方法、构造方法、私有方法和父类方法，其他的都为Virtual Call

Receiver objects：方法调用对应的实例对象（static方法调用不需要对应实例）

Target methods：表达IR指令到被调用目标方法的映射关系

Num of target methods：call对应的可能被调用的目标方法的数量。Virtual call与动态绑定和多态实现有关，可以对应多个对象下的重写方法。所以Virtual call的可能对象可能超过1个

Determinacy：指什么时候能够确定这个call的对应方法。Virtual call与多态有关，只能在运行时决定调用哪一个具体方法的实现。其他两种call都和多态机制不相关，编译时刻就可以确定

Method Dispatch of Virtual Calls

virtual call 在程序运行时才能得到，virtual call 基于2个要素

1. receiver object的type
2. call site的方法签名（method signature）

方法签名由以下部分组成

Signature = class type + method name + descriptor 
Descriptor = return type + parameter types

用 Dispatch(c, m) 来模拟动态 Method Dispatch 过程，c 表示 receiver object，m 表示函数签名

示例如下：

Class Hierarchy Analysis (CHA)

Definition of CHA

Require the class hierarchy information (inheritance structure) of the whole program

Resolve a virtual call based on the declared type of receiver variable of the call site

Assume the receiver variable a may point to objects of class A or all subclasses of A（Resolve target methods by looking up the class hierarchy of class A）

对一个 call site 执行 Resolve 方法得到所有可能的 target methods 算法如下

示例如下：

CHA的优势是速度快原因是只考虑call site中receiver variable的declared type和它的继承结构还有忽略数据流和控制流信息

CHA的劣势是精度较低原因是容易引入虚假目标方法和没有使用指针分析

Call Graph Construction

Build call graph for whole program via CHA

Start from entry methods (focus on main method)

For each reachable method 𝑚, resolve target methods for each call site 𝑐𝑠 in 𝑚 via CHA (Resolve(𝑐𝑠))

Repeat until no new method is discovered

从入口方法开始（例如对于Java而言的main方法）对于每一个可达方法m，在方法m中通过CHA算法为每一个call site计算目标方法一直到重复这个过程直到没有新的方法被发现

示例如下：

Interprocedural Control-Flow Graph

ICFG = CFGs + call & return edges

Call edges: from call sites to the entry nodes of their callees

Return edges: from exit nodes of the callees to the statementsfollowing their call sites (i.e., return sites)

示例如下：


Interprocedural Data-Flow Analysis


4种transfer函数

Node transfer

Edge transfer

• Call edge transfer
• Return edge transfer
• Node transfer 每一个函数调用都要kill掉LHS（Left hand side）的变量

示例如下：